/*
package demo1;

import javax.swing.tree.TreeNode;
import java.util.Stack;

public class Solution1 {
    class Solution {
        //寻找根节点到目标节点的路径
        private boolean getPath (TreeNode root, TreeNode p, Stack stack) {
            if (root == null) {
                return false;
            }
            stack.push(root);
            if (root == p) {
                return true;
            }
            boolean flg = getPath(root.left,p,stack);
            if (flg) {
                return true;
            }
            flg = getPath(root.right,p,stack);
            if (flg) {
                return true;
            }
            stack.pop();
            return false;
        }
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            Stack<TreeNode> stack1 = new Stack<>();
            getPath(root,p,stack1);
            Stack<TreeNode> stack2 = new Stack<>();
            getPath(root,q,stack2);
            int size1 = stack1.size();
            int size2 = stack2.size();
            if (size1 > size2) {
                int size = size1 - size2;
                while (size != 0) {
                    stack1.pop();
                    size--;
                }
                while (!stack1.empty()) {
                    if (stack1.peek() == stack2.peek()) {
                        return stack1.pop();
                    } else {
                        stack1.pop();
                        stack2.pop();
                    }
                }
            } else {
                int size = size2 - size1;
                while (size != 0) {
                    stack2.pop();
                    size--;
                }
                while (!stack2.empty()) {
                    if (stack1.peek() == stack2.peek()) {
                        return stack1.pop();
                    } else {
                        stack1.pop();
                        stack2.pop();
                    }
                }
            }
            return null;

        }
    }
}
*/
